Pengantar Graf:
BFS & DFS
👩🏫 Secara Formal:
Graf (Graph) adalah struktur data yang terdiri dari simpul (Node/Vertex) dan garis penghubung (Edge). Graf digunakan untuk memodelkan jaringan jalan, pertemanan, dll.
- Adjacency Matrix: Cara menyimpan graf menggunakan tabel 2D, di mana baris dan kolom adalah Node, dan isinya (0/1) penanda ada Edge atau tidak.
- BFS (Breadth-First Search): Algoritma pencarian yang menelusuri secara melebar. Mengunjungi tetangga terdekat dulu (layer per layer) memakai antrian (Queue).
- DFS (Depth-First Search): Algoritma pencarian yang menelusuri secara mendalam. Masuk terus sampai mentok, lalu mundur (backtrack) memakai tumpukan (Stack).
Analogi Jaman Now
BFS (Air Tumpah)
Bayangkan kamu menumpahkan segelas air di tengah lapangan. Air itu akan menyebar ke segala arah secara perlahan dan merata, dari ring 1, ke ring 2, lalu ring 3. Cocok banget buat cari Jalan Terpendek!
DFS (Orang Nyasar)
Kamu masuk ke labirin. Pokoknya tiap ketemu belokan, kamu belok KIRI terus sampai mentok jalan buntu. Kalau mentok, kamu putar balik nyari belokan lain yang belum dicoba. Cocok buat mencari apakah ada "jalan keluar" atau tidak.
Pencarian Labirin (BFS vs DFS)
Pilih algoritma dan perhatikan cara penyebarannya dari START menuju END.
⚠️ Common Mistakes: Lupa Array "Visited" (Infinite Loop)
Kesalahan paling sering (dan fatal) saat menulis kode BFS atau DFS adalah lupa menandai node yang sudah dikunjungi (menggunakan array visited[node] = true). Jika lupa, algoritma akan bolak-balik mengecek node A ke B, lalu B ke A secara terus-menerus. Akibatnya: program akan terjebak dalam Infinite Loop (TLE) atau mengalami Stack Overflow (RTE) karena terlalu banyak rekursi!
Pilih Strategi Eksekusi:
Builder Adjacency Matrix
Ubah hubungan antar kota (Node). Klik baris/kolom tabel untuk membuat jalur penghubung (Edge), dan perhatikan bagaimana graf disamping akan berubah secara dinamis (Tersambung/Tidak).
⚠️ Common Mistakes: Memory Limit Exceeded (MLE)
Banyak pemula selalu menggunakan Adjacency Matrix (array 2D adj[V][V]) untuk merepresentasikan graf. Hati-hati! Jika jumlah kota (V) mencapai $100.000$, ukuran array menjadi $100.000 \times 100.000 = 10$ Miliar elemen. Hal ini akan memakan memori puluhan Gigabyte dan menyebabkan Memory Limit Exceeded (MLE). Untuk Graf berukuran besar (Sparse Graph), selalu gunakan struktur Adjacency List (List dari tetangga).